package _01_排序;

import java.util.ArrayList;
import java.util.List;
/*
    希尔排序:
    ◼ 希尔排序把序列看作是一个矩阵，分成 𝑚 列，逐列进行排序
    𝑚 从某个整数逐渐减为1
    当 𝑚 为1时，整个序列将完全有序
    时间复杂度：最好、平均O(n),最坏O(n^2),属于不稳定的排序
 */
public class ShellSort07<E extends Comparable<E>> extends Sort<E> {
    @Override
    protected void sort() {
        List<Integer> stepSequence = shellStepSequence();
        System.out.println(stepSequence);
        for (Integer step : stepSequence) {
            sort(step);
        }
    }

    /**
     * 分成step列进行排序
     * 内部因为逆序对越来越少，使用插入排序
     * @param step
     */
    private void sort(int step){
        //从第一列开始
        for(int col=0;col<step;col++){
            //内部使用插入排序，假设第一个已经排好序，从第二个开始，索引索引为col+step
            for(int begin = col+step;begin<array.length;begin += step){
                int cur = begin; //记录当前的索引
                //cur必须要大于当前列的索引，第一个默认有序，不需要比较，不然无法保证在同一列
                while(cur>col && cmp(cur,cur-step)<0){
                    swap(cur,cur-step);
                    cur -= step;
                }
            }
        }
    }

    /**
     *  生成步长序列的方法
      * @return
     */
    private List<Integer> shellStepSequence(){
        List<Integer> stepSequence = new ArrayList<>();
        int step = array.length;
        while((step >>= 1) >0){
            stepSequence.add(step);
        }
        return stepSequence;
    }
}
